The networking of control units, sensors and actuator systems with the aid of a communications system or bus system has drastically increased in recent years in the construction of modern motor vehicles and in machine construction, especially in the field of machine tools and in automation. In this context, synergistic effects may be achieved by the distribution of functions to a plurality of control units. These are called distributed systems. The communication between various stations is taking place more and more via a bus or a bus system. The communications traffic on the bus, access and reception mechanisms, as well as error handling are governed via a protocol.
In the automotive field, the established protocol is the CAN (controller area network). This is an event-driven protocol, i.e., protocol activities such as sending a message are initiated by events which have their origin outside of the communications system. Unique access to the communications system is solved by a priority-based bit arbitration. A prerequisite for this is that a unique priority is assigned to each message. When working with the CAN protocol, this is usually implemented by an identifier which is contained at the beginning of each message and clearly identifies the message content. This identifier or identification ID (message identifier) is of different length depending on the CAN version (e.g., 11 bits for the basic CAN). The CAN protocol is very flexible, and adding additional nodes and messages is possible without difficulty as long as there are still free priorities (especially message identifiers). The collection of all messages to be sent in the network together with priorities is stored in a list, the so-called communications matrix. Thus, in most cases, the creation of the communications matrix is only the collection of all messages in the system. Frequently, the order or sequence of the messages is based on the years-long know-how of the applications engineers and system designers. However, tools also exist which support this creation of the communications matrices.
An alternative approach to the event-driven, spontaneous communication is the purely time-controlled approach. All communications activities on the bus are strictly periodic. Protocol activities such as sending a message are triggered only by the advance in a (global) time. Access to the medium is based on the assignment of time domains during which a transmitter has an exclusive transmission right. The protocol is comparatively inflexible, and adding new nodes is only possible when the respective time domains were already left open beforehand. This situation forces the system designer or applications engineer to already fix the message sequence prior to initial operation. Thus, a timetable or bus schedule is created which must meet the requirements of the messages with respect to rate of repetition, redundancy, deadlines, etc. Therefore, this so-called bus schedule is a timetable or time schedule or sequence plan or communications plan with respect to transmitting messages on the bus. The positioning of the messages within the transmission periods must be matched to the applications which produce the message contents, in order to hold the latencies between application and moment of transmission to a minimum. If this matching does not take place, the advantage of the time-controlled transmission (minimal latency jitter when sending the message on the bus) would be destroyed. Thus, great demands are placed on the planning tools.
The solution approach set forth in German Patent Application No. DE 100 00 302, DE 100 00 303, DE 100 00 304, DE 100 00 305 and also presented in the ISO draft 11898-4, of the time-controlled or time-triggered CAN satisfies the demands outlined above for time-controlled communication, as well as the demands for a certain measure of flexibility. This so-called TTCAN (time-triggered controller area network) meets these demands by the construction of the communications round (basic cycle) in so-called exclusive time windows for periodic messages of specific communications users and in so-called arbitrating time windows for spontaneous messages of a plurality of communications users. However, as described above, when planning a TTCAN network or TTCAN bus system, the time-controlled messages will predetermine the framework for the creation of the bus schedule. The requirements of the time-controlled communication must also be optimally supported or guaranteed in a TTCAN communications matrix or bus schedule or time schedule for the transmission of messages. Only in the second instance may the event-driven messages or arbitrating time windows be taken into account. The suitable planning tools must, as it were, support both worlds of the communications planning.
Great demands are placed on the planning tools for the time-controlled communication and the resolution of the communications relationships (application with respect to the moment of transmitting the message on the bus) in the form of a communications matrix, including the message latencies, message periods and deadlines. Currently available commercial tools, particularly CAN-based tools, still do not support these requirements, such as, for example, TTCAN-specific planning, at all. First solution approaches for strictly time-controlled communications protocols such as TTP/C show that the algorithms to be used quickly end up as an NP-complete problem. The discovery of the global maximum, thus, the best solution for the entire communications network with respect to the bus schedule, cannot be guaranteed. Possibly only quantities of sub-optimal solutions for a bus schedule are found using conventional search algorithms.
Moreover, genetic algorithms are known in the related art. Projects such as VLSI, circuit-layout-generation based on genetic algorithms or the solution of nonlinear equations via genetic algorithms (for fitting potential surfaces) use this technique. A citation from D. Goldberg “Genetic Algorithms in Search, Optimization & Machine Learning” from the Addison-Wesley Publishing Company Inc. of January 1989 shows the basic idea of genetic algorithms: “Genetic algorithms are search algorithms based on the mechanics of natural selection and natural genetics. They combine survival of the fittest among string structures with a structured yet randomized information exchange to form a search algorithm with some of the innovative flair of human search. In every generation, a new set of artificial creatures (strings) is created using bits and pieces of the fittest of the old; an occasional new part is tried for good measure. While randomized, genetic algorithms are no simple random walk. They efficiently exploit historical information to speculate on new search points with expected improved performance.”
This approach to alternative searches for solutions in immensely large solution areas had the goal of abstracting and explaining the adaptive processes of the natural systems. That is to say, in principle, the genetic algorithms are based on natural selection or genetic selection. Survival principles, such as the survival of the fittest, are combined with population or solution structures and the exchange of information arising in this context. Thus, in each generation, new populations or solutions are created which use parts of the best of the old generations. In contrast to genetic algorithms, many functions F supply a wide divergence and discontinuous results, and are therefore unsuitable for many traditional approaches of the search for solutions F(x). Genetic algorithms avoid this problem by simulating the natural evolution according to the Darwinian model.
An object of the present invention is to overcome the problems touched upon with respect to the planning of the time schedule or timetable of the bus, thus of the bus schedule.